package org.hegang.algorithm.bubblesort;


import java.util.Arrays;

/**
 * @ClassName BubbleSort
 * @Describe: [冒泡排序]
 * @Author: gang.he
 * @Email: SmileSkylife@outlook.com
 * @Date: Created in 23:28 2019/6/27
 * @Modified By:
 * @Version V1.0
 */
public class BubbleSort {
    /**
     * 未优化的冒泡排序
     *
     * @param bubbleSort
     * @return
     */
    public void bubbleSort(int[] bubbleSort) {
        if (bubbleSort == null || bubbleSort.length == 0) {
            return;
        }
        System.out.println("数组长度： " + bubbleSort.length);
        //两两比教，总共需要轮询比较总数-1次
        for (int i = 0; i < bubbleSort.length - 1; i++) {
            //内循环会随着每轮结束减少一次比较次数，因为最大的数最后一定在末位。
            for (int j = 0; j < bubbleSort.length - i - 1; j++) {
                if (bubbleSort[j] > bubbleSort[j + 1]) {
                    int temp = bubbleSort[j];
                    bubbleSort[j] = bubbleSort[j + 1];
                    bubbleSort[j + 1] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(bubbleSort));
    }

    /**
     * 优化后的冒泡排序
     *
     * @param bubbleSort
     * @return
     */
    public void optimizationBubbleSort(int[] bubbleSort) {
        //外层循环优化,一旦有序，立即退出排序
        for (int i = 0; i < bubbleSort.length - 1; i++) {
            boolean flag = true;
            for (int j = 0; j < bubbleSort.length - i - 1; j++) {
                if (bubbleSort[j] > bubbleSort[j + 1]) {
                    int temp = bubbleSort[j];
                    bubbleSort[j] = bubbleSort[j + 1];
                    bubbleSort[j + 1] = temp;
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
        System.out.println(Arrays.toString(bubbleSort));
    }
}
